package 数学作业.homework3.test1;

import java.util.Random;

public class 希尔排序 {
    public static void main(String[] args) {
            Random ran = new Random();
            int[] arr = new int[100];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = ran.nextInt(101);
            }
            shell(arr);
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
    }

    public static void shell(int[] arr){
        int size = arr.length;
        while(size > 1){
            //这里注意对每次的间隔进行变化
            size = size / 3 + 1;
            //每一个size对应一整次的遍历
            for(int i = size;i < arr.length;i++){
                int key = arr[i];
                int end = i - size;
                while(end >= 0 && arr[end] > key){
                    arr[end + size] = arr[end];
                    end -= size;
                }
                arr[end + size] = key;
            }
        }
    }
}
